//  https://leetcode-cn.com/problems/3sum/
//  ThreeCountSum.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/27.
//  Copyright © 2019 XFB. All rights reserved.
//  三数和

import Foundation

class ThreeCountSum {
    
    /**
     给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
     注意：答案中不可以包含重复的三元组。
     
     例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     满足要求的三元组集合为：
     [
     [-1, 0, 1],
     [-1, -1, 2]
     ]
     */
    
    func threeSum(_ nums: [Int]) -> [[Int]] {
        
        var tuples = [[Int]]()
        
        if nums.count < 3 {
            return tuples
        }
        
        /// -4, -1, -1, 0, 1, 2
        var sortedNums = nums.sorted()

        for i in 0 ..< sortedNums.count {
            
            if sortedNums[i] > 0 {
                /// 停止遍历
                break
            }
            
            if i > 0 && sortedNums[i] == sortedNums[i-1] {
                /// 跳过此次遍历
                continue
            }
            
            /// 左边界
            var left = i + 1
            /// 右边界
            var right = sortedNums.count - 1
            
            while left < right {
                let sum = sortedNums[i] + sortedNums[left] + sortedNums[right]
                
                if right < sortedNums.count - 1 && sortedNums[right] == sortedNums[right + 1] || sum > 0 {
                    right = right - 1
                } else if left > i + 1 && sortedNums[left] == sortedNums[left - 1] || sum < 0 {
                    left = left + 1
                } else {
                    var list = [Int]()
                    list.append(sortedNums[i])
                    list.append(sortedNums[left])
                    list.append(sortedNums[right])
                    tuples.append(list)
                    left = left + 1
                    right = right - 1
                }
            }
        }
        return tuples
    }
    
    
    
    
    func threeSum1(_ nums: [Int]) -> [[Int]] {

        var tuples = [[Int]]()

        guard nums.count >= 3 else {
            return tuples
        }
        
        var sortedNums = nums.sorted()
        
        for index in 0 ..< sortedNums.count {
            
            if sortedNums[index] > 0 {
                break
            }
            
            if index > 0 && sortedNums[index] == sortedNums[index - 1] {
                continue
            }
            
            var left = index + 1
            var right = sortedNums.count - 1
            
            while left < right {
                let sum = sortedNums[index] + sortedNums[left] + sortedNums[right]
                if sum > 0 {
                    right = right - 1
                } else if sum < 0 {
                    left = left + 1
                } else {
                    var list = [Int]()
                    list.append(sortedNums[index])
                    list.append(sortedNums[left])
                    list.append(sortedNums[right])
                    tuples.append(list)
                  
                    /// 去重 ??
//                    while left > index + 1 && sortedNums[left] == sortedNums[left - 1] {
                    while left < right && sortedNums[left] == sortedNums[left + 1] {
                        left = left + 1
                    }
                    
//                    while right < sortedNums.count - 1 && sortedNums[right] == sortedNums[right + 1] {
                    while left < right && sortedNums[right] == sortedNums[right - 1] {
                        right = right - 1
                    }
                
                    left = left + 1
                    right = right - 1
                }
            }
        }
        return tuples
    }
    
    
    func threeSum2(_ nums: [Int]) -> [[Int]] {

        var sortedNums = nums.sorted(by: <)

        var tuples = [[Int]]()
        
        if sortedNums.count <= 2 {
            return tuples
        }
        
        for i in 0 ... sortedNums.count - 3 {
            
            
            if i == 0 || sortedNums[i] != sortedNums[i-1] {
                let remain = -sortedNums[i]
                var left = i + 1
                var right = nums.count - 1
                
                while left < right {
                    if sortedNums[left] + sortedNums[right] == remain { /// 等于 去重
                        var list = [Int]()
                        list.append(sortedNums[i])
                        list.append(sortedNums[left])
                        list.append(sortedNums[right])
                        tuples.append(list);
                        
                        repeat {
                            left = left + 1
                        } while left < right && sortedNums[left] == sortedNums[left - 1]
                        
                        repeat {
                            right = right - 1
                        } while left < right && sortedNums[right] == sortedNums[right + 1]
                        
                    } else if sortedNums[left] + sortedNums[right] < remain { /// 小于 左边界右侧移动一位
                        repeat {
                            left = left + 1
                        } while left < right && sortedNums[left] == sortedNums[left - 1]
                    } else { // 大于 右边界左侧移动一位
                        repeat {
                            right = right - 1
                        } while left < right && sortedNums[right] == sortedNums[right + 1]
                    }
                }
            }
        }
        return tuples

    }
    
    
}
